package com.zxy.javaarithmetic.dynamic_program;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.dynamic_program
 *  @文件名:   JKDynamicUtils
 *  @创建者:   zhangxy
 *  @创建时间:  2019/10/30 15:54
 *  @描述：    动态规划法(来自极客时间，王争老师的数据结构与算法之美课程)
 */
public class JKDynamicUtils {

	/**
	 * 计算两个字符串的莱文斯坦距离（a数组经过最少次添加、删除、修改等操作可以变成b字符数组）
	 * @param a  字符串a
	 * @param n  a字符数组长度
	 * @param b  字符串b
	 * @param m  b字符串长度
	 * @return
	 */
	public static int lwstDP(char[] a, int n, char[] b, int m) {
		int[][] minDist = new int[n][m];
		for (int j = 0; j < m; ++j) { // 初始化第0行:a[0..0]与b[0..j]的编辑距离
			if (a[0] == b[j]) minDist[0][j] = j;
			else if (j != 0) minDist[0][j] = minDist[0][j - 1] + 1;
			else minDist[0][j] = 1;
		}
		for (int i = 0; i < n; ++i) { // 初始化第0列:a[0..i]与b[0..0]的编辑距离
			if (a[i] == b[0]) minDist[i][0] = i;
			else if (i != 0) minDist[i][0] = minDist[i - 1][0] + 1;
			else minDist[i][0] = 1;
		}
		for (int i = 1; i < n; ++i) { // 按行填表
			for (int j = 1; j < m; ++j) {
				if (a[i] == b[j])
					minDist[i][j] = min(minDist[i - 1][j] + 1, minDist[i][j - 1] + 1, minDist[i - 1][j - 1]);
				else
					minDist[i][j] = min(minDist[i - 1][j] + 1, minDist[i][j - 1] + 1, minDist[i - 1][j - 1] + 1);
			}
		}
		return minDist[n - 1][m - 1];
	}

	private static int min(int x, int y, int z) {
		int minv = Integer.MAX_VALUE;
		if (x < minv) minv = x;
		if (y < minv) minv = y;
		if (z < minv) minv = z;
		return minv;
	}

	/**
	 * 题目来自：极客时间40：初识动态规划法  课后思考题
	 * @param matrix 杨辉三角形二维数组
	 * @return
	 */
	public static int yanghuiTriangle(int[][] matrix) {
		//杨辉三角形宽高是一样的
		int[][] state = new int[matrix.length][matrix.length];
		state[0][0] = matrix[0][0];

		for (int i = 1; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				if (j == 0) {
					state[i][j] = state[i - 1][j] + matrix[i][j];
				} else if (j == matrix[i].length - 1) {
					state[i][j] = state[i - 1][j - 1] + matrix[i][j];
				} else {
					//
					int left = state[i - 1][j - 1];
					int right = state[i - 1][j];
					state[i][j] = Math.min(left, right) + matrix[i][j];
				}
			}
		}

//		for (int i = 0; i < state.length; i++) {
//			for (int j = 0; j < state[i].length; j++) {
//				System.out.print(state[i][j]+"--");
//			}
//			System.out.println("");
//		}

		int min = Integer.MAX_VALUE;
		for (int i = 0; i < state[state.length-1].length; i++) {
			if (state[state.length - 1][i] < min) {
				min = state[state.length - 1][i];
			}
		}

		return min;
	}


}
